package Q15

import java.util.Arrays

import java.util.ArrayList

fun main() {

}

class Main {

}

class Solution {
    fun threeSum(nums: IntArray?): List<List<Int>> {
        val ans: MutableList<List<Int>> = ArrayList()
        if (nums == null || nums.size <= 2) return ans
        Arrays.sort(nums) // O(nlogn)
        for (i in 0 until nums.size - 2) {
            if (nums[i] > 0) break
            if (i > 0 && nums[i] == nums[i - 1]) continue
            val target = -nums[i]
            var left = i + 1
            var right = nums.size - 1
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(ArrayList(Arrays.asList(nums[i], nums[left], nums[right])))
                    left++
                    right--
                    while (left < right && nums[left] == nums[left - 1]) left++
                    while (left < right && nums[right] == nums[right + 1]) right--
                } else if (nums[left] + nums[right] < target) {
                    left++
                } else {
                    right--
                }
            }
        }
        return ans
    }
}